"""
题目:
给定n个非负整数表示每个宽度为1的柱子的高度图,
计算按此排列的柱子,下雨之后能接多少雨水?
"""


def after_rain(height):
    length = len(height)
    # 小于等于2根柱子的情况,接不到雨水,至少需要3根柱子
    if height is None or length <= 2:
        return 0
    # 用一个列表记录每根柱子(位置)能接到的雨水
    water = []
    for i in range(length):
        # 判断左边最大数
        if i == 0:
            lmax = 0
        elif i == 1:
            lmax = height[0]
        else:
            lmax = max(height[:i])
        # 判断右边最大数
        if i == length - 1:
            rmax = 0
        elif i == length - 2:
            rmax = height[length-1]
        else:
            rmax = max(height[i+1:])
        # 左右最大数中取较小值 再和 当前柱子高度作差
        delta = min(lmax, rmax) - height[i]
        if delta <= 0:
            water.append(0)
        else:
            water.append(delta)
    return sum(water)


height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
water = after_rain(height)
print(water)

